package org.leetcode.easy;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;

public class IntersectTwo {
    // 350. 两个数组的交集 II
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        if (nums1.length <= nums2.length) {
            return binarySearchRun(nums1, nums2);
        } else {
            return binarySearchRun(nums2, nums1);
        }
    }

    public int[] binarySearchRun(int[] minNums, int[] maxNums) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < minNums.length; i++) {
            int j;
            if ((j = binarySearch(maxNums, minNums[i], 0, maxNums.length - 1)) >= 0) {
                list.add(maxNums[j]);
                maxNums[j] = -1;
            }
            Arrays.sort(maxNums);
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
    public int binarySearch(int[] nums, int target, int left, int right) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            return binarySearch(nums, target, left, mid - 1);
        } else if (nums[mid] < target) {
            return binarySearch(nums, target, mid + 1, right);
        }
        return -1;
    }

    @Test
    public void test() {
        int[] nums1 = {1,2,2,1};
        int[] nums2 = {1,1};
        System.out.println(Arrays.toString(intersect(nums1, nums2)));
    }
}
